Matrice d'adjacence - Méthode

La matrice d’adjacence  \(A\) permet de retrouver le degré des sommets du graphe \(G\) .

Si le graphe  \(G\)  n'est pas orienté, la somme des coefficients de la ligne  \(i\) , qui est égale à   la somme des coefficients de la colonne  \(i\) , donne le degré du sommet  \(i\) .

Si le graphe  \(G\)  est orienté :

• la somme des coefficients de la ligne  \(i\)  donne le degré sortant du sommet  \(i\)  ;
  
• la somme des coefficients de la ligne  \(i\)  donne le degré entrant du sommet.
  

Exemple 1

Ici,  \(G\) n’est pas orienté et il est d’ordre \(9\) .

Sa matrice d’adjacence est symétrique de taille \(9 \times 9\) .

\(A=\begin{pmatrix}0 & 1 & 0&0 & 0 & 0&0 & 0 & 0\\1 & 0 & 0&1 & 1 & 1&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\\0 & 1 & 0&0 & 1 & 0&0 & 0 & 0\\0 & 1 & 0&1 & 0 & 0&1 & 1& 0\\0 & 1 &1&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0&1\\0&0&0&0&0&1&0&1&0\end{pmatrix}\)

En réalisant les sommes par lignes (ou colonnes), on retrouve les degrés des sommets :

\(\begin{array}{|c|c|} \hline \text {Sommet}&1&2&3&4&5&6&7&8&9 \\ \hline \text {Degré}&1&4&1&2&4&3&1&2&2\\ \hline \end{array}\)

Exemple 2

Ici,  \(G\) est orienté et il est d’ordre \(9\) .

Sa matrice d’adjacence est de taille  \(9 \times 9\) mais n’est pas symétrique.

\(A= \begin{pmatrix}0 & 0 & 0&1 & 0 & 0&0 & 0 & 0\\1 & 0 & 1&1 & 0 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\\0 & 0 & 0&0 & 1 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 0&1 & 1& 1\\0 & 1 & 1&0 & 0 & 0&0 & 0 & 0\\0 & 0 & 0&0 & 0 & 0&0 & 1 & 0\\0 & 0 & 0&0 & 0 & 0&0 & 0 & 1\\0 & 0 & 0&0 & 0 & 1&0 & 0 & 0\end{pmatrix}\)

En réalisant les sommes par lignes, on retrouve les degrés sortants des sommets et par colonnes les degrés entrants :

\(\begin{array}{|c|c|} \hline \text {Sommet}&1&2&3&4&5&6&7&8&9 \\ \hline \text {Degré sortant}&1&3&1&1&3&2&1&1&1\\ \hline \text {Degré entrant}&1&1&2&2&1&2&1&2&2\\ \hline \end{array}\)